package leetcode;

import util.TreeNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0105.java
 * @Author : WangRuoyu
 * @Date 2023/11/11 21:42
 */


public class Q0105 {
    private TreeNode createTree(int[] preorder, int[] inorder, int l1, int r1, int l2, int r2) {
        if (l1 > r1) return null;
        TreeNode node = new TreeNode(preorder[l1]);
        int k = l2;
        for (; k <= r2; k++) {
            if (inorder[k] == node.val) break;
        }
        node.left = createTree(preorder, inorder, l1 + 1, l1 + k - l2, l2, k - 1);
        node.right = createTree(preorder, inorder, l1 + k - l2 + 1, r1, k + 1, r2);
        return node;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return createTree(preorder, inorder, 0, preorder.length - 1, 0, preorder.length - 1);
    }

    public static void main(String[] args) {
        Q0105 sl = new Q0105();
        int[] preorder = {3, 9, 20, 15, 7};
        int[] inorder = {9, 3, 15, 20, 7};
        TreeNode root = sl.buildTree(preorder, inorder);
    }
}